package 滑动窗口And双指针.双指针;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/12 21:33
 */
public class leetcode42接雨水 {
    /*
     非常经典的 一道题目!
     灵神 基础算法 视频 中， 是有讲解的！
     灵神的讲解:
     https://www.bilibili.com/video/BV1Qg411q7ia/?vd_source=179da737184de5a8f84e4f6c2ee5c350

     双指针是他妈 最比较好用的!


     - 把 数组的每一个位置,都看成有一个桶, 然后 计算  数组每个位置的桶, 能接多少雨水, 进行累加就行了
     如果有疑惑的的话, 可以看下灵神这里的讲解
     */



    //  时间复杂度 O(N), 空间复杂度 O(N)
    public int solve(int nums[]){
        // 使用两个数组
        int len = nums.length;
        int preMax[] = new int[len], sufMax[] = new int[len], ans = 0;
        preMax[0] = nums[0];
        for(int i = 1;i  < len;i++){
            preMax[i] = Math.max(preMax[i - 1],nums[i]);
        }
        sufMax[len - 1] = nums[len - 1];
        for(int i = len - 2;i >= 0;i--){
            sufMax[i] = Math.max(nums[i],sufMax[i - 1]);
        }
        // 遍历 nums 的每个 位置 开始 统计 每个位置水桶能够 装多少水
        for(int i = 0;i < len;i++){
            ans += Math.min(preMax[i],sufMax[i]) - nums[i];
        }
        return ans;
    }


    // 优化空间的做法, 双指针
    public int solve2(int nums[]){
        int l = 0, r = nums.length - 1,ans = 0,preMax = 0,sufMax = 0;
        while(l <= r){ // l == r 位置 也是有桶的, 每个 位置上都有一个桶
            preMax = Math.max(preMax,nums[l]);
            sufMax = Math.max(sufMax,nums[r]);
            if(preMax < sufMax){
                ans += preMax - nums[l];
                l++;

            }else{
                ans += sufMax - nums[r];
                r--;
            }
        }

        return ans;
    }

}
class A{

    public  synchronized void  fa(){
        System.out.println("a");
    }
    public void f(){

    }


}
class B extends A{
    public synchronized void fb(){
        super.fa();

    }

}
